MST: Complexity Comparison

Core Principle: The Cut Property

If we partition the vertices $V$ into two sets, $S$ and $V-S$, the minimum weight edge crossing this boundary (the cut) must belong to some MST of $G$. This is the foundation of greedy MST algorithms.

1. Prim’s Algorithm (Vertex-Centric)

Starts at an arbitrary vertex.
Similar to Dijkstra's, it uses a Priority Queue to repeatedly select and add the cheapest edge connecting a vertex in the growing tree to a vertex outside the tree.

2. Kruskal’s Algorithm (Edge-Centric)

Sorts all edges $E$ by weight in non-decreasing order.
Iterates through the sorted edges, adding an edge if and only if it does not create a cycle. This is typically handled by a Disjoint Set Union (DSU) structure.

Complexity Comparison

The choice between Prim's and Kruskal's often depends on the graph density, where $|V|=N$ and $|E|=M$.

Algorithm	Key Data Structure	Time (Sparse)	Time (Dense $M \approx N^2$)
Prim's	Priority Queue (Min-Heap)	$O(M \log N)$	$O(N^2)$ (using array)
Kruskal's	Disjoint Set Union (DSU)	$O(M \log M)$	$O(M \log N)$

*Note: Kruskal's complexity is often written as $O(M \log M + M \alpha(N))$, where $\alpha(N)$ is the nearly constant Inverse Ackermann function from DSU operations. For simplicity, $O(M \log M)$ is used as sorting dominates.

📝 Interactive Quiz

1. Sparse Graph Scenario: A network graph has 1,000 vertices ($|V|=1,000$) and only 1,500 edges ($|E|=1,500$). Which algorithm is theoretically best suited for this sparse case?

A) Prim’s Algorithm using a Fibonacci Heap ($O(M + N \log N)$)
B) Kruskal’s Algorithm ($O(M \log M)$)
C) Prim’s Algorithm using an array ($O(V^2)$)
D) Floyd-Warshall Algorithm

2. Dense Graph Scenario: You are given a dense graph with 500 vertices and nearly 125,000 edges ($|E| \approx |V|^2$). Which implementation is likely the most efficient?

A) Kruskal's Algorithm ($O(M \log M)$)
B) Prim's Algorithm using a min-heap ($O(M \log N)$)
C) Prim's Algorithm using an adjacency matrix/array ($O(V^2)$)
D) Bellman-Ford Algorithm

3. Kruskal's Core Logic: What is the most critical condition Kruskal's algorithm must check before adding a sorted edge to the MST?

A) If the edge connects to the starting vertex.
B) If the edge has the lowest possible weight in the entire graph.
C) If adding the edge creates a cycle.
D) If the edge's destination is already in the tree.

4. Prim's vs. Dijkstra: Both algorithms are greedy and use a priority queue. What is the fundamental difference in the value they prioritize?

A) Prim's prioritizes total path cost from a source; Dijkstra prioritizes individual edge weights.
B) Prim's prioritizes individual edge weights to connect to the tree; Dijkstra prioritizes total path cost from a source.
C) There is no fundamental difference; they are the same algorithm.
D) Prim's works on undirected graphs; Dijkstra only works on directed graphs.

KEY TIPS

💡 Key Tips

Quiz Rationale

Kruskal's is best for sparse graphs ($M \approx N$) because sorting few edges is fast. Prim's ($O(V^2)$ version) is best for dense graphs ($M \approx N^2$) as it avoids logarithmic factors.

When to use Kruskal’s?

Best for sparse graphs where $|E|$ is close to $|V|$. Its performance depends on sorting edges, not on graph structure.

When to use Prim’s?

Best for dense graphs where $|E|$ approaches $|V|^2$. The $O(V^2)$ implementation using an adjacency matrix outperforms others here.

Prim's vs. Dijkstra

Both are greedy and use a Priority Queue. Prim's tracks the minimum edge weight to connect to the tree. Dijkstra tracks the minimum path weight from the source.